package cn.com.caluation;

import java.util.Arrays;

public class SortTest2 {
    /*
    * 快速排序
    * 每一轮排序选择一个基准点,将大于基准点的元素放入一个分区,小于基准点的元素放入另外一个分区
    * 分区结束,基准点元素的位置为最终位置
    * 在子分区内重复以上过程，直至子分区元素个数少于等于 1，这体现的是分而治之的思想
    *
    * */

    /*
    * 快速排序
    * 单边循环快排
    * 选择最右的元素为基准点
    *
    *
    * */

    public int[] quick(int[] a,int l,int h){
        if(l >= h){
            return a;
        }

        int p = partion(a,l,h);
        quick(a,l,p-1); //左边分区
        quick(a,p+1,h); //右边分区
        return a;
    }

    public int[] quick2(int[] a,int l,int h){
        if(l >= h){
            return a;
        }

        int p = partion2(a,l,h);
        quick2(a,l,p-1); //左边分区
        quick2(a,p+1,h); //右边分区
        return a;
    }

    private int partion(int[] a,int l,int h){
        int pv = a[h];//基准点数据
        int i = l;
        for(int j = l;j < h;j++){
            if(a[j] < pv){
                if( i != j){
                    swap(a,i,j);
                }
                i++;
            }
        }

        swap(a,h,i);

        return i;
    }

    private void swap(int[] a,int i,int j){
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }


    /*
    * 快速排序
    * 双边循环
    * 以最左边的元素为基准点
    * j 指针负责从右向左找比基准点小的元素，i 指针负责从左向右找比基准点大的元素，一旦找到二者交换，直至 i，j 相交
    * 最后基准点与 i（此时 i 与 j 相等）交换，i 即为分区位置
    *
    *
    * */
    private int  partion2(int[] a,int l,int h){
        int pv = a[l];
        int i = l;
        int j = h;

        while (j > i){

            while (j > i && pv < a[j]){
                j--;
            }

            while (j >i && pv >= a[i]){
                i++;
            }

            swap(a,i,j);
        }

        swap(a,l,j);
        return j;
    }


    public static void main(String[] args) {
        SortTest2 sortTest2 = new SortTest2();
        int[] array3 = {1,4,6,7,15,33,39,1,5,8,11,19};

       array3 = sortTest2.quick2(array3,0,array3.length - 1);

        System.out.println(Arrays.toString(array3));
    }
}
